package com.sig.formes;

import java.util.ArrayList;
import java.util.List;

public class EarCuttingSimply {

	public static int pointplusagauche(List<Point> points){
		Point p = points.get(0);
		int pos = 0;
		for(int i = 0 ; i < points.size();i++){
			
			if(p.x > points.get(i).x){
				p = points.get(i);
				pos = i ;
			}
		}
		return pos;
	}

	public static List<Triangle> trianguler(List<Point> points){

		List<Triangle> triangles = new ArrayList<Triangle>();
		Point central;
		Point gauche;
		Point droit;
		Point gaucheDeLaDroite;
		if(points.size() >= 3){
			// Si on a plus qu'un triangle
			if(points.size() == 3){
			
				triangles.add(new Triangle(points.get(1), points.get(2), points.get(0)));
			}else{

				// Pour tous les points
					// Si on est sur le premier point
				int pos = pointplusagauche(points);
				
				if(pos == 0){
					central = points.get(pos);
					gauche = points.get(pos+1);
					droit = points.get(points.size()-1);

				}else{
					if(pos == points.size()-1){
						central = points.get(pos);
						gauche = points.get(0);
						droit = points.get(pos-1);

					}else{
						central = points.get(pos);
						gauche = points.get(pos+1);
						droit = points.get(pos-1);

					}
				}
						

					// On cherche s'il y a un point plus à gauche et qu'il ne soit pas central
					gaucheDeLaDroite = trouverPointGauche(central,gauche,droit,points);

					// Si il existe pas on créer un triangle
					if(gaucheDeLaDroite == null){

						triangles.add(new Triangle(central,gauche, droit));
						List<Point> polynome_premier = new ArrayList<Point>();
						Point tmps = gauche;
						int j = pos+1 ;
						// On récupère le premier polygone
						do{
							if(j > points.size() - 1)
								j = 0;
							tmps = points.get(j);
							polynome_premier.add(tmps);
							j++;
						}	while(!tmps.equals(droit));
						
						triangles.addAll(trianguler(polynome_premier));

						
					}else{

						// Sinon on coupe le polygone en deux
						List<Point> polynome_premier = new ArrayList<Point>();
						List<Point> polynome_second = new ArrayList<Point>();
						Point tmps = central;
						int j = pos;
						// On récupère le premier polygone
						do{
							if(j > points.size() - 1)
								j = 0;
							tmps = points.get(j);
							polynome_premier.add(tmps);
							j++;
						}	while(!tmps.equals(gaucheDeLaDroite));

						j = points.indexOf(gaucheDeLaDroite);

						// On récupère le second polygone
						do{
							if(j > points.size() - 1)
								j = 0;

							tmps = points.get(j);
							polynome_second.add(tmps);
							j++;
						}	while(!tmps.equals(central));

						// On triangule ces polygones
						triangles.addAll(trianguler(polynome_premier));
						triangles.addAll(trianguler(polynome_second));

					}
				
			}
		}
		return triangles;
	}
/*
	private static Point trouverPointGauche(Point central,Point gauche, Point droit,List<Point> points) {
		Point p = null;
		for(int i = 0 ; i < points.size()-1;i++){

			if(!points.get(i).equals(central) && !points.get(i).equals(gauche) && !points.get(i).equals(droit)){
				if(     ( determinant( central, gauche,  points.get(i) ) > 0 )
						&&      ( determinant( gauche, droit, points.get(i) ) > 0 )
						&&      ( determinant( droit, central,points.get(i) ) > 0 )
						)
				{

					p = points.get(i);
				}
				
				if(     ( determinant( central, gauche, points.get(i) ) < 0 )
						&&      ( determinant( gauche, droit,points.get(i) ) < 0 )
						&&      ( determinant( droit, central, points.get(i) ) < 0 )
						)
				{
					p = points.get(i);
				}
			}

		}
		return p;

	}
	*/
	private static Point trouverPointGauche(Point central,Point gauche, Point droit,List<Point> points) {
		Point p = null;
		// Result: >0 si newp est à gauche de la droite P1-P2
		//		           =0 si le point est surla droite
		//		          <0 ... droite
		// NB : surface du triangle = Isleft / 2 .
		// chaque point défini par ses coordonnées X,Y ...
		float result;
		for(int i = 0 ; i < points.size()-1;i++){

			if(!points.get(i).equals(central) && !points.get(i).equals(gauche) && !points.get(i).equals(droit)){
				result = (droit.x - gauche.x) * (points.get(i).y - gauche.y) - (points.get(i).x - gauche.x)*(droit.y - gauche.x);

				if(result >= 0){
					if(p == null){
						p = points.get(i);
					}else{
						if(points.get(i).x < p.x){
							p = points.get(i);

						}
					}
				}
			}

		}
		return p;

	}

	public static List<Triangle> trianguler(Polyedre poly){
		List<Point> points = poly.getPoints();
		return trianguler(points);
	}
}
